import java.io.*;
import java.math.BigInteger;
import java.util.*;
 
/**
 * @author Egor Kulikov (egor@egork.net)
 */
public class AllInOne {
	@SuppressWarnings({"FieldCanBeLocal", "UnusedDeclaration"})
	private InputReader in;
	private PrintWriter out;
	private static boolean testMode = false;
 
	private Solver[] solvers = {
//		new SuccessiveAdding(),
		new WeightedDecision2(10, 0),
		new WeightedDecision2(14, 1),
//		new WeightedDecision2(6, 2),
		new WeightedDecision2(6, 3),
		new WeightedDecision2(9, 4),
//		new WeightedDecision2(11, 3),
//		new WeightedDecision2(10, 0),
//		new WeightedDecision2(9, 3),
//		new WeightedDecision2(7, 3),
//		new WeightedDecision2(11, 2),
//		new WeightedDecision2(14, 3),
//		new WeightedDecision2(12, 3),
//		new WeightedDecision2(10, 3),
//		new WeightedDecision2(8, 3),
//		new WeightedDecision2(13, 1),
//		new WeightedDecision2(12, 1),
//		new WeightedDecision2(15, 3),
//		new WeightedDecision2(11, 5),
//		new SuccessiveAddingWeightedCluster()
	};
 
	private Map<String,Double> results;
	private Map<String,Integer> best;
	private double total = 0;
	private double[] sqrtWeights = null;
	private int[] weightedDistances;
	private int[] order;
	private int lastPower;
 
	{
		results = new HashMap<String, Double>();
		best = new HashMap<String, Integer>();
		for (Solver solver : solvers) {
			results.put(solver.getClass().getName(), 0.);
			best.put(solver.getClass().getName(), 0);
		}
	}
 
	private void solve() {
		Arrays.sort(solvers, new Comparator<Solver>() {
			public int compare(Solver o1, Solver o2) {
				boolean isWD1 = o1 instanceof WeightedDecision2;
				boolean isWD2 = o2 instanceof WeightedDecision2;
				if (!isWD1) {
					if (!isWD2)
						return 0;
					return 1;
				}
				if (!isWD2)
					return -1;
				return ((WeightedDecision2) o1).power - ((WeightedDecision2) o2).power;
			}
		});
		int vertexCount = in.readInt();
		int edgeCount = in.readInt();
		int customerCount = in.readInt();
		@SuppressWarnings({"unchecked"})
		List<Integer>[] customers = new List[vertexCount];
		for (int i = 0; i < vertexCount; i++) {
			customers[i] = new ArrayList<Integer>();
		}
		for (int i = 0; i < customerCount; i++) {
			customers[in.readInt()].add(i + 1);
		}
		Graph graph = new BidirectionalGraph(vertexCount);
		for (int i = 0; i < edgeCount; i++) {
			int from = in.readInt();
			int to = in.readInt();
			int cost = in.readInt();
			graph.addEdge(new WeightedEdge(from, to, cost));
		}
		final int[][] distances = floydWarshall(graph);
//		final int[][] distances = new int[vertexCount][];
//		for (int i = 0; i < vertexCount; i++)
//			distances[i] = dijkstra(graph, i).distance;
		int[] weights = new int[vertexCount];
		for (int i = 0; i < vertexCount; i++)
			weights[i] = customers[i].size();
		int[] result = chooser(vertexCount, customerCount, weights, distances);
		List<Integer> totalResult = new ArrayList<Integer>();
		for (int index : result)
			totalResult.addAll(customers[index]);
		out.print(totalResult.get(0));
		for (int i = 1; i < customerCount; i++) {
			out.print(" " + totalResult.get(i));
		}
		out.println();
	}
 
	private interface Solver {
		public int[] solve(int vertexCount, int customerCount, int[] weights, int[][] distances);
	}
 
	private int[] chooser(int vertexCount, int customerCount, int[] weights, final int[][] distances) {
		int[] result = null;
		long cost = Long.MAX_VALUE;
		String name = null;
		sqrtWeights = new double[vertexCount];
		weightedDistances = new int[vertexCount * vertexCount];
		order = new int[vertexCount * vertexCount];
		lastPower = -1;
		for (Solver solver : solvers) {
			int[] currentResult = solver.solve(vertexCount, customerCount, weights, distances);
			long currentCost = calculateCost(weights, distances, currentResult, currentResult.length);
			results.put(solver.getClass().getName(), results.get(solver.getClass().getName()) + currentCost / (
				(double)customerCount));
			if (currentCost < cost) {
				cost = currentCost;
				result = currentResult;
				name = solver.getClass().getName();
			}
		}
		best.put(name, best.get(name) + 1);
		total += ((double) cost) / customerCount;
		sqrtWeights = null;
		return result;
	}
 
	private long calculateCost(int[] weights, int[][] distances, int[] result, int resultSize) {
		long cost = 0;
		long length = 0;
		for (int i = 1; i < resultSize; i++) {
			length += distances[result[i - 1]][result[i]];
			cost += length * weights[result[i]];
		}
		return cost;
	}
 
	private class SuccessiveAdding implements Solver {
		public int[] solve(int vertexCount, int customerCount, final int[] weights, int[][] distances) {
			int toVisit = 1;
			for (int i = 1; i < vertexCount; i++) {
				if (weights[i] != 0)
					toVisit++;
			}
			int[] result = new int[toVisit];
			result[0] = 0;
			int resultSize = 1;
			int orderSize = 0;
			Integer[] order = new Integer[toVisit - 1];
			for (int i = 1; i < vertexCount; i++) {
				if (weights[i] != 0)
					order[orderSize++] = i;
			}
			Arrays.sort(order, new Comparator<Integer>() {
				public int compare(Integer o1, Integer o2) {
					return weights[o2] - weights[o1];
				}
			});
			long currentCost = 0;
			long currentLength = 0;
			int totalCustomers = 0;
			for (int i = 0; i < toVisit - 1; i++) {
				int index = order[i];
				long bestCost = currentCost + (currentLength + distances[result[resultSize - 1]][index]) *
					weights[index];
				int bestIndex = i + 1;
				int remainingCustomers = totalCustomers;
				long startLength = 0;
				for (int j = 1; j <= i; j++) {
					int previous = result[j - 1];
					int next = result[j];
					long current = currentCost + (startLength + distances[previous][index]) * weights[index] +
							remainingCustomers * (distances[previous][index] + distances[index][next] - distances[previous][next]);
					if (current < bestCost) {
						bestCost = current;
						bestIndex = j;
					}
					remainingCustomers -= weights[next];
					startLength += distances[previous][next];
				}
				//noinspection ManualArrayCopy
				for (int j = resultSize; j > bestIndex; j--)
					result[j] = result[j - 1];
				result[bestIndex] = index;
				resultSize++;
				totalCustomers += weights[index];
				localOptimizationsShort(vertexCount, totalCustomers, weights, distances, result, resultSize);
				currentCost = calculateCost(weights, distances, result, resultSize);
				currentLength = calculateDistance(result, resultSize, distances);
			}
			localOptimizations(vertexCount, customerCount, weights, distances, result);
			return result;
		}
	}
 
	private class SuccessiveAddingWeightedCluster implements Solver {
		public int[] solve(int vertexCount, int customerCount, final int[] weights, int[][] distances) {
			int toVisit = 1;
			for (int i = 1; i < vertexCount; i++) {
				if (weights[i] != 0)
					toVisit++;
			}
			int[] result = new int[toVisit];
			result[0] = 0;
			int resultSize = 1;
			int orderSize = 0;
			Integer[] order = new Integer[toVisit - 1];
			for (int i = 1; i < vertexCount; i++) {
				if (weights[i] != 0)
					order[orderSize++] = i;
			}
			final int[] myWeight = new int[vertexCount];
			for (int i = 0; i < vertexCount; i++) {
				if (weights[i] == 0)
					continue;
				for (int j = 0; j < vertexCount; j++) {
					if (distances[i][j] <= 100)
						myWeight[i] += weights[j];
				}
			}
			Arrays.sort(order, new Comparator<Integer>() {
				public int compare(Integer o1, Integer o2) {
					return myWeight[o2] - myWeight[o1];
				}
			});
			long currentCost = 0;
			long currentLength = 0;
			int totalCustomers = 0;
			for (int i = 0; i < toVisit - 1; i++) {
				int index = order[i];
				long bestCost = currentCost + (currentLength + distances[result[resultSize - 1]][index]) *
					weights[index];
				int bestIndex = i + 1;
				int remainingCustomers = totalCustomers;
				long startLength = 0;
				for (int j = 1; j <= i; j++) {
					int previous = result[j - 1];
					int next = result[j];
					long current = currentCost + (startLength + distances[previous][index]) * weights[index] +
							remainingCustomers * (distances[previous][index] + distances[index][next] - distances[previous][next]);
					if (current < bestCost) {
						bestCost = current;
						bestIndex = j;
					}
					remainingCustomers -= weights[next];
					startLength += distances[previous][next];
				}
				//noinspection ManualArrayCopy
				for (int j = resultSize; j > bestIndex; j--)
					result[j] = result[j - 1];
				result[bestIndex] = index;
				resultSize++;
				totalCustomers += weights[index];
				localOptimizationsShort(vertexCount, totalCustomers, weights, distances, result, resultSize);
				currentCost = calculateCost(weights, distances, result, resultSize);
				currentLength = calculateDistance(result, resultSize, distances);
			}
			localOptimizations(vertexCount, customerCount, weights, distances, result);
			return result;
		}
	}

	private class SuccessiveAddingCluster implements Solver {
		public int[] solve(int vertexCount, int customerCount, final int[] weights, int[][] distances) {
			int toVisit = 1;
			for (int i = 1; i < vertexCount; i++) {
				if (weights[i] != 0)
					toVisit++;
			}
			int[] result = new int[toVisit];
			result[0] = 0;
			int resultSize = 1;
			int[] order = clustering(vertexCount, weights, distances, toVisit - 1);
			long currentCost = 0;
			long currentLength = 0;
			int totalCustomers = 0;
			for (int i = 0; i < toVisit - 1; i++) {
				int index = order[i];
				long bestCost = currentCost + (currentLength + distances[result[resultSize - 1]][index]) *
					weights[index];
				int bestIndex = i + 1;
				int remainingCustomers = totalCustomers;
				long startLength = 0;
				for (int j = 1; j <= i; j++) {
					int previous = result[j - 1];
					int next = result[j];
					long current = currentCost + (startLength + distances[previous][index]) * weights[index] +
							remainingCustomers * (distances[previous][index] + distances[index][next] - distances[previous][next]);
					if (current < bestCost) {
						bestCost = current;
						bestIndex = j;
					}
					remainingCustomers -= weights[next];
					startLength += distances[previous][next];
				}
				//noinspection ManualArrayCopy
				for (int j = resultSize; j > bestIndex; j--)
					result[j] = result[j - 1];
				result[bestIndex] = index;
				resultSize++;
				totalCustomers += weights[index];
				localOptimizationsShort(vertexCount, totalCustomers, weights, distances, result, resultSize);
				currentCost = calculateCost(weights, distances, result, resultSize);
				currentLength = calculateDistance(result, resultSize, distances);
			}
			localOptimizations(vertexCount, customerCount, weights, distances, result);
			return result;
		}
 
		private int[] clustering(final int vertexCount, int[] weights, final int[][] distances, int viable) {
			Integer[] edges = new Integer[viable * (viable - 1) / 2];
			int index = 0;
			for (int i = 0; i < vertexCount; i++) {
				if (weights[i] == 0)
					continue;
				for (int j = 0; j < i; j++) {
					if (weights[j] == 0)
						continue;
					edges[index++] = i * vertexCount + j;
				}
			}
			Arrays.sort(edges, new Comparator<Integer>() {
				public int compare(Integer o1, Integer o2) {
					return distances[o1 / vertexCount][o1 % vertexCount] - distances[o2 / vertexCount][o2 % vertexCount];
				}
			});
			final int[] myWeights = new int[vertexCount];
			System.arraycopy(weights, 0, myWeights, 0, vertexCount);
			int[] s = new int[vertexCount];
			for (int i = 0; i < vertexCount; i++)
				s[i] = i;
			@SuppressWarnings({"unchecked"})
			List<Integer>[] children = new List[vertexCount];
			for (int i = 0; i < vertexCount; i++) {
				if (weights[i] != 0)
					children[i] = new ArrayList<Integer>();
			}
//			int steps = (int) (viable - Math.sqrt(viable));
			int[] order = new int[viable];
			for (int i : edges) {
//				if (steps == 0)
//					break;
				int from = i / vertexCount;
				int to = i % vertexCount;
				if (distances[from][to] > 100)
					break;
				from = get(s, from);
				to = get(s, to);
				if (from != to) {
//					steps--;
					if (myWeights[from] < myWeights[to]) {
						myWeights[to] += myWeights[from];
						s[from] = to;
						children[to].add(from);
					} else {
						myWeights[from] += myWeights[to];
						s[to] = from;
						children[from].add(to);
					}
				}
			}
			List<Integer> roots = new ArrayList<Integer>();
			for (int i = 0; i < vertexCount; i++) {
				if (weights[i] != 0 && s[i] == i) {
					roots.add(i);
				}
			}
			Collections.sort(roots, new Comparator<Integer>() {
				public int compare(Integer o1, Integer o2) {
					return myWeights[o2] - myWeights[o1];
				}
			});
			index = 0;
			for (int root : roots)
				index = fill(order, root, index, children);
			return order;
		}
 
		private int fill(int[] order, int root, int index, List<Integer>[] children) {
			order[index++] = root;
			for (int i = 0; i < children[root].size(); i++)
				index = fill(order, children[root].get(i), index, children);
			return index;
		}
 
		private int get(int[] s, int v) {
			if (s[v] == v)
				return v;
			return s[v] = get(s, s[v]);
		}
	}

	private class WeightedDecision2 implements Solver {
		private final int variants;
		private final int power;


		public WeightedDecision2(int variants, int power) {
			this.variants = variants;
			this.power = power;
		}

		private long estimate(int vertexCount, long remainingCustomers, int[] weights, final int[] distances,
							  boolean[] visited, int start, int[] stillViable, int[][] simpleDistances, int[] order, int[] orderIndex, int interestingVertexCount, int totalToTravel) {
			long result = 0;
			boolean[] localVisited = new boolean[vertexCount];
			System.arraycopy(visited, 0, localVisited, 0, vertexCount);
			localVisited[start] = true;
			while (remainingCustomers != 0) {
				int shift = start * vertexCount;
				int bestValue = Integer.MAX_VALUE;
				int bestIndex = -1;
				if (1 + orderIndex[start] + stillViable.length * totalToTravel < interestingVertexCount) {
					for (int i : stillViable) {
						if (!localVisited[i]) {
							int cost = distances[shift + i];
							if (cost < bestValue) {
								bestValue = cost;
								bestIndex = i;
							}
						}
					}
				} else {
					for (int i = orderIndex[start]; ; i++) {
						if (!localVisited[order[shift + i]]) {
							bestIndex = order[shift + i];
							break;
						}
					}
				}
//				if (bestIndex == -1)
//					break;
				localVisited[bestIndex] = true;
				result += simpleDistances[start][bestIndex] * remainingCustomers;
				remainingCustomers -= weights[bestIndex];
				start = bestIndex;
				totalToTravel--;
			}
			return result;
		}
 
		public int[] solve(int vertexCount, int customerCount, final int[] weights, final int[][] distances) {
			boolean[] visited = new boolean[vertexCount];
			int totalToTravel = vertexCount;
			for (int i = 0; i < vertexCount; i++) {
				visited[i] = weights[i] == 0;
				if (visited[i]) {
					totalToTravel--;
				}
			}
			int currentVertex = 0;
			int[] result = new int[totalToTravel + 1];
			result[0] = 0;
			int lastIndex = 1;
			int remainingCustomers = customerCount;
//			if (sqrtWeights == null)
			createWeights(vertexCount, weights, distances, visited, totalToTravel);
			int[] orderIndex = new int[vertexCount];
			int interestingVertexCount = totalToTravel;
			while (totalToTravel != 0) {
				int[] stillViable = new int[totalToTravel];
				int viableIndex = 0;
				for (int i = 0; i < vertexCount; i++) {
					if (!visited[i]) {
						stillViable[viableIndex++] = i;
					}
				}
				for (int i : stillViable) {
					while (orderIndex[i] < interestingVertexCount && visited[order[i * vertexCount + orderIndex[i]]])
						orderIndex[i]++;
				}
				int[] results = new int[variants];
				int[] indices = new int[variants];
				int bestCount = 0;
				for (int j : stillViable) {
					int currentResult = weightedDistances[currentVertex * vertexCount + j];
					if (bestCount < variants) {
						results[bestCount] = currentResult;
						indices[bestCount++] = j;
					} else if (results[variants - 1] > currentResult) {
						results[variants - 1] = currentResult;
						indices[variants - 1] = j;
					}
					for (int k = bestCount - 1; k > 0; k--) {
						if (results[k] < results[k - 1]) {
							int temp = results[k];
							results[k] = results[k - 1];
							results[k - 1] = temp;
							int intTemp = indices[k];
							indices[k] = indices[k - 1];
							indices[k - 1] = intTemp;
						}
					}
				}
				long best = Long.MAX_VALUE;
				int index = -1;
				for (int k = 0; k < bestCount; k++) {
					int j = indices[k];
					long currentWeight = ((long) distances[currentVertex][j]) * remainingCustomers + estimate(vertexCount, remainingCustomers - weights[j], weights, weightedDistances, visited, j, stillViable, distances, order, orderIndex, interestingVertexCount, totalToTravel - 1);
					if (currentWeight < best) {
						best = currentWeight;
						index = j;
					}
				}
				List<Integer> toVisit = new ArrayList<Integer>();
				for (int j = 0; j < vertexCount; j++) {
					if (!visited[j] && distances[currentVertex][j] + distances[j][index] ==
						distances[currentVertex][index]) {
						toVisit.add(j);
					}
				}
				final int finalCurrentVertex = currentVertex;
				Collections.sort(toVisit, new Comparator<Integer>() {
					public int compare(Integer o1, Integer o2) {
						return distances[finalCurrentVertex][o1] - distances[finalCurrentVertex][o2];
					}
				});
				int lastVisited = currentVertex;
				for (int vertex : toVisit) {
					if (distances[lastVisited][index] == distances[lastVisited][vertex] + distances[vertex][index]) {
						totalToTravel--;
						result[lastIndex++] = vertex;
						visited[vertex] = true;
						lastVisited = vertex;
						remainingCustomers -= weights[vertex];
					}
				}
				currentVertex = index;
			}
			localOptimizations(vertexCount, customerCount, weights, distances, result);
			return result;
		}

		private void createWeights(int vertexCount, int[] weights, int[][] distances, boolean[] visited, int totalToTravel) {
			if (power == lastPower)
				return;
			lastPower = power;
			for (int i = 0; i < vertexCount; i++) {
				if (!visited[i]) {
					double value = -1;
					switch (power) {
						case 0:
							value = 1;
							break;
						case 1:
							value = Math.sqrt(Math.sqrt(weights[i]));
							break;
						case 2:
							value = Math.sqrt(weights[i]);
							break;
						case 3:
							double sqrt = Math.sqrt(weights[i]);
							value = sqrt * Math.sqrt(sqrt);
							break;
						case 4:
							value = weights[i];
							break;
						case 5:
							double sqrt2 = Math.sqrt(weights[i]);
							value = sqrt2 * Math.sqrt(Math.sqrt(sqrt2));
							break;
					}
					sqrtWeights[i] = value;
				}
			}
			for (int i = 0; i < vertexCount; i++) {
				for (int j = 0; j < vertexCount; j++) {
					if (visited[j])
						continue;
					weightedDistances[i * vertexCount + j] = (int) (distances[i][j] * 10000 / sqrtWeights[j]);
				}
			}
			for (int i = 0; i < vertexCount; i++) {
				if (visited[i])
					continue;
				Integer[] localOrder = new Integer[totalToTravel - 1];
				int localIndex = 0;
				for (int j = 0; j < vertexCount; j++) {
					if (visited[j] || i == j)
						continue;
					localOrder[localIndex++] = j;
				}
				final int shift = i * vertexCount;
				Arrays.sort(localOrder, new Comparator<Integer>() {
					public int compare(Integer o1, Integer o2) {
						return weightedDistances[shift + o1] - weightedDistances[shift + o2];
					}
				});
				for (int j = 0; j < totalToTravel - 1; j++)
					order[i * vertexCount + j] = localOrder[j];
			}
		}
	}

	private class WeightedRandomDecision2 implements Solver {
		private final Random rnd;
		private final int power;


		public WeightedRandomDecision2(int seed, int power) {
			rnd = new Random(seed);
			this.power = power;
		}

		private long estimate(int vertexCount, long remainingCustomers, int[] weights, final int[] distances,
							  boolean[] visited, int start, int[] stillViable, int[][] simpleDistances, int[] order, int[] orderIndex, int interestingVertexCount, int totalToTravel) {
			long result = 0;
			boolean[] localVisited = new boolean[vertexCount];
			System.arraycopy(visited, 0, localVisited, 0, vertexCount);
			localVisited[start] = true;
			while (remainingCustomers != 0) {
				int shift = start * vertexCount;
				int bestValue = Integer.MAX_VALUE;
				int bestIndex = -1;
				if (1 + orderIndex[start] + stillViable.length * totalToTravel < interestingVertexCount) {
					for (int i : stillViable) {
						if (!localVisited[i]) {
							int cost = distances[shift + i];
							if (cost < bestValue) {
								bestValue = cost;
								bestIndex = i;
							}
						}
					}
				} else {
					for (int i = orderIndex[start]; ; i++) {
						if (!localVisited[order[shift + i]]) {
							bestIndex = order[shift + i];
							break;
						}
					}
				}
//				if (bestIndex == -1)
//					break;
				localVisited[bestIndex] = true;
				result += simpleDistances[start][bestIndex] * remainingCustomers;
				remainingCustomers -= weights[bestIndex];
				start = bestIndex;
				totalToTravel--;
			}
			return result;
		}

		public int[] solve(int vertexCount, int customerCount, final int[] weights, final int[][] distances) {
			boolean[] visited = new boolean[vertexCount];
			int totalToTravel = vertexCount;
			for (int i = 0; i < vertexCount; i++) {
				visited[i] = weights[i] == 0;
				if (visited[i]) {
					totalToTravel--;
				}
			}
			int currentVertex = 0;
			int[] result = new int[totalToTravel + 1];
			result[0] = 0;
			int lastIndex = 1;
			int remainingCustomers = customerCount;
//			if (sqrtWeights == null)
			createWeights(vertexCount, weights, distances, visited, totalToTravel);
			int[] orderIndex = new int[vertexCount];
			int interestingVertexCount = totalToTravel;
			while (totalToTravel != 0) {
				int[] stillViable = new int[totalToTravel];
				int viableIndex = 0;
				for (int i = 0; i < vertexCount; i++) {
					if (!visited[i]) {
						stillViable[viableIndex++] = i;
					}
				}
				for (int i : stillViable) {
					while (orderIndex[i] < interestingVertexCount && visited[order[i * vertexCount + orderIndex[i]]])
						orderIndex[i]++;
				}
				int variants = (int) Math.sqrt(totalToTravel);
				int[] results = new int[variants];
				int[] indices = new int[variants];
				int bestCount = 0;
				for (int j : stillViable) {
					int currentResult = weightedDistances[currentVertex * vertexCount + j];
					if (bestCount < variants) {
						results[bestCount] = currentResult;
						indices[bestCount++] = j;
					} else if (results[variants - 1] > currentResult) {
						results[variants - 1] = currentResult;
						indices[variants - 1] = j;
					}
					for (int k = bestCount - 1; k > 0; k--) {
						if (results[k] < results[k - 1]) {
							int temp = results[k];
							results[k] = results[k - 1];
							results[k - 1] = temp;
							int intTemp = indices[k];
							indices[k] = indices[k - 1];
							indices[k - 1] = intTemp;
						}
					}
				}
				long best = Long.MAX_VALUE;
				int index = -1;
				for (int k = 0; k < bestCount; k++) {
					int j = indices[k];
					long currentWeight = ((long) distances[currentVertex][j]) * remainingCustomers + estimate(vertexCount, remainingCustomers - weights[j], weights, weightedDistances, visited, j, stillViable, distances, order, orderIndex, interestingVertexCount, totalToTravel - 1);
					if (currentWeight < best) {
						best = currentWeight;
						index = j;
					}
				}
				List<Integer> toVisit = new ArrayList<Integer>();
				for (int j = 0; j < vertexCount; j++) {
					if (!visited[j] && distances[currentVertex][j] + distances[j][index] ==
						distances[currentVertex][index]) {
						toVisit.add(j);
					}
				}
				final int finalCurrentVertex = currentVertex;
				Collections.sort(toVisit, new Comparator<Integer>() {
					public int compare(Integer o1, Integer o2) {
						return distances[finalCurrentVertex][o1] - distances[finalCurrentVertex][o2];
					}
				});
				int lastVisited = currentVertex;
				for (int vertex : toVisit) {
					if (distances[lastVisited][index] == distances[lastVisited][vertex] + distances[vertex][index]) {
						totalToTravel--;
						result[lastIndex++] = vertex;
						visited[vertex] = true;
						lastVisited = vertex;
						remainingCustomers -= weights[vertex];
					}
				}
				currentVertex = index;
			}
			localOptimizations(vertexCount, customerCount, weights, distances, result);
			return result;
		}

		private void createWeights(int vertexCount, int[] weights, int[][] distances, boolean[] visited, int totalToTravel) {
			if (power == lastPower)
				return;
			lastPower = power;
			for (int i = 0; i < vertexCount; i++) {
				if (!visited[i]) {
					double value = -1;
					switch (power) {
						case 0:
							value = 1;
							break;
						case 1:
							value = Math.sqrt(Math.sqrt(weights[i]));
							break;
						case 2:
							value = Math.sqrt(weights[i]);
							break;
						case 3:
							double sqrt = Math.sqrt(weights[i]);
							value = sqrt * Math.sqrt(sqrt);
							break;
						case 4:
							value = weights[i];
							break;
						case 5:
							value = Math.pow(weights[i], 2. / 3);
							break;
					}
					sqrtWeights[i] = value;
				}
			}
			for (int i = 0; i < vertexCount; i++) {
				for (int j = 0; j < vertexCount; j++) {
					if (visited[j])
						continue;
					weightedDistances[i * vertexCount + j] = (int) (distances[i][j] * 10000 / sqrtWeights[j]);
				}
			}
			for (int i = 0; i < vertexCount; i++) {
				if (visited[i])
					continue;
				Integer[] localOrder = new Integer[totalToTravel - 1];
				int localIndex = 0;
				for (int j = 0; j < vertexCount; j++) {
					if (visited[j] || i == j)
						continue;
					localOrder[localIndex++] = j;
				}
				final int shift = i * vertexCount;
				Arrays.sort(localOrder, new Comparator<Integer>() {
					public int compare(Integer o1, Integer o2) {
						return weightedDistances[shift + o1] - weightedDistances[shift + o2];
					}
				});
				for (int j = 0; j < totalToTravel - 1; j++)
					order[i * vertexCount + j] = localOrder[j];
			}
		}
	}

	private long calculateDistance(int[] result, int resultSize, int[][] distances) {
		long answer = 0;
		for (int i = 1; i < resultSize; i++)
			answer += distances[result[i - 1]][result[i]];
		return answer;
	}
 
	private void localOptimizationsShort(int vertexCount, int customerCount, int[] weights,
		int[][] distances, int[] result, int resultSize)
	{
		if (resultSize <= 1)
			return;
		for (int j = 0; j < vertexCount * vertexCount; j++) {
			long remainingWeight = customerCount - weights[result[1]];
			boolean updated = false;
			for (int i = 1; i < resultSize - 2; i++) {
				int first = result[i];
				int second = result[i + 1];
				int last = result[i - 1];
				int next = result[i + 2];
				remainingWeight -= weights[second];
				long totalWeight = weights[first] + weights[second] + remainingWeight;
				long current = distances[last][first] * totalWeight + distances[first][second] * (totalWeight -
					weights[first]) + remainingWeight * distances[second][next];
				long possible = distances[last][second] * totalWeight + distances[second][first] * (totalWeight -
					weights[second]) + remainingWeight * distances[first][next];
				if (possible < current) {
					result[i] = second;
					result[i + 1] = first;
					updated = true;
					break;
				}
			}
			if (!updated) {
				break;
			}
		}
	}
 
	private void localOptimizations(int vertexCount, int customerCount, int[] weights, int[][] distances, int[] result) {
		localOptimizationsShort(vertexCount, customerCount, weights, distances, result, result.length);
		for (int l = 0; l < vertexCount; l++) {
			boolean updated = false;
			long cost = calculateCost(weights, distances, result, result.length);
			long outerRemaining = customerCount - weights[result[1]];
			long outerLength = distances[0][result[1]];
			for (int i = 2; i < result.length; i++) {
				final int index = result[i];
				final int outerLast = result[i - 1];
				final int outerEdge = distances[outerLast][index];
				outerLength += outerEdge;
				outerRemaining -= weights[index];
				long outerCost = cost - outerLength * weights[index];
				if (i != result.length - 1) {
					final int outerNext = result[i + 1];
					outerCost -= outerRemaining * (outerEdge + distances[index][outerNext] - distances[outerLast][outerNext]);
				}
				long innerRemaining = customerCount - weights[index];
				long innerLength = 0;
				for (int j = 1; j < i; j++) {
					final int innerLast = result[j - 1];
					final int innerNext = result[j];
					final int innerEdge = distances[innerLast][innerNext];
					long innerCost = outerCost + (innerLength + distances[innerLast][index]) * weights[index] +
						innerRemaining * (distances[innerLast][index] + distances[index][innerNext] - innerEdge);
					if (innerCost < cost) {
						cost = innerCost;
						//noinspection ManualArrayCopy
						for (int k = i; k > j; k--)
							result[k] = result[k - 1];
						result[j] = index;
						updated = true;
						break;
					}
					innerLength += innerEdge;
					innerRemaining -= weights[innerNext];
				}
				if (updated)
					break;
			}
			if (!updated)
				break;
		}
	}
 
	public static int[][] floydWarshall(Graph graph) {
		int vertexCount = graph.getVertexCount();
		int[][] distance = new int[vertexCount][vertexCount];
		for (int[] row : distance) {
			Arrays.fill(row, Integer.MAX_VALUE);
		}
		for (int i = 0; i < vertexCount; i++) {
			for (Edge edge : graph.getIncident(i)) {
				distance[i][edge.getDestination()] = edge.getWeight();
			}
			distance[i][i] = 0;
		}
		for (int i = 0; i < vertexCount; i++) {
			for (int j = 0; j < vertexCount; j++) {
				for (int k = j + 1; k < vertexCount; k++) {
					if (distance[j][i] != Integer.MAX_VALUE && distance[i][k] != Integer.MAX_VALUE) {
						distance[k][j] = distance[j][k] = Math.min(distance[j][k], distance[j][i] + distance[i][k]);
					}
				}
			}
		}
		return distance;
	}
 
	public interface Edge {
		public int getSource();
 
		public int getDestination();
 
		public int getWeight();
 
		public Edge getTransposedEdge();
	}
 
	public static class SimpleEdge implements Edge {
		protected final int source;
		protected final int destination;
 
		public SimpleEdge(int source, int destination) {
			this.source = source;
			this.destination = destination;
		}
 
		public int getSource() {
			return source;
		}
 
		public int getDestination() {
			return destination;
		}
 
		public int getWeight() {
			return 1;
		}
 
		public Edge getTransposedEdge() {
			return new TransposedEdge(this);
		}
	}
 
	public static class WeightedEdge extends SimpleEdge {
		protected final int weight;
 
		public WeightedEdge(int source, int destination, int weight) {
			super(source, destination);
			this.weight = weight;
		}
 
		@Override
		public int getWeight() {
			return weight;
		}
 
		@Override
		public Edge getTransposedEdge() {
			return new WeightedEdge(destination, source, weight);
		}
	}
 
	public static class TransposedEdge implements Edge {
		private final Edge parent;
 
		public TransposedEdge(Edge parent) {
			this.parent = parent;
		}
 
		public int getSource() {
			return parent.getDestination();
		}
 
		public int getDestination() {
			return parent.getSource();
		}
 
		public int getWeight() {
			return parent.getWeight();
		}
 
		public Edge getTransposedEdge() {
			return parent;
		}
	}
 
	public interface Graph {
		public int getVertexCount();
 
		public List<Edge> getIncident(int source);
 
		public void addEdge(Edge edge);
 
	}
 
	public static class BidirectionalGraph extends SparseGraph {
		public BidirectionalGraph(int vertexCount) {
			super(vertexCount);
		}
 
		@Override
		public void addEdge(Edge edge) {
			super.addEdge(edge);
			super.addEdge(edge.getTransposedEdge());
		}
 
	}
 
	public static class SparseGraph implements Graph {
		private final int vertexCount;
		private final List<Edge>[] edges;
 
		public SparseGraph(int vertexCount) {
			this.vertexCount = vertexCount;
			//noinspection unchecked
			edges = new List[vertexCount];
			for (int i = 0; i < vertexCount; i++) {
				edges[i] = new ArrayList<Edge>();
			}
		}
 
		public int getVertexCount() {
			return vertexCount;
		}
 
		public void addEdge(Edge edge) {
			edges[edge.getSource()].add(edge);
		}
 
		public List<Edge> getIncident(int source) {
			return edges[source];
		}
	}
 
	public static void main(String[] args) {
		if (args.length > 0 && args[0].equals("42"))
			testMode = true;
		new AllInOne().run();
	}
 
	private AllInOne() {
		@SuppressWarnings({"UnusedDeclaration"})
		String id = getClass().getName().toLowerCase();
		//noinspection EmptyTryBlock
		try {
//			System.setIn(new FileInputStream(id + ".in"));
//			System.setOut(new PrintStream(new FileOutputStream(id + ".out")));
//			if (testMode) {
//				System.setIn(new FileInputStream("input.txt"));
//				System.setOut(new PrintStream(new FileOutputStream("output.txt")));
//			}
		} catch (Exception e) {
			throw new RuntimeException(e);
		}
		if (testMode) {
			in = new StringInputReader(generateTests());
			out = new PrintWriter(new Writer() {
				@Override
				public void write(char[] cbuf, int off, int len) throws IOException {
				}
 
				@Override
				public void flush() throws IOException {
				}
 
				@Override
				public void close() throws IOException {
				}
			});
		} else {
			in = new StreamInputReader(System.in);
			out = new PrintWriter(System.out);
		}
	}
 
	@SuppressWarnings({"StringConcatenationInsideStringBufferAppend"})
	private String generateTests() {
		StringBuilder builder = new StringBuilder();
		builder.append("30\n");
		Random rnd = new Random(239);
		for (int i = 0; i < 10; i++) {
			builder.append("300 2000 10000\n");
			for (int j = 0; j < 10000; j++)
				builder.append(" " + (rnd.nextInt(299) + 1));
			builder.append("\n");
			for (int j = 0; j < 2000; j++)
				builder.append(rnd.nextInt(300) + " " + rnd.nextInt(300) + " " + (rnd.nextInt(1000) + 1) + "\n");
		}
		for (int i = 0; i < 10; i++) {
			builder.append("300 598 10000\n");
			for (int j = 0; j < 10000; j++)
				builder.append(" " + (rnd.nextInt(299) + 1));
			builder.append("\n");
			for (int j = 1; j < 300; j++) {
				builder.append(j + " " + rnd.nextInt(j) + " " + (rnd.nextInt(1000) + 1) + "\n");
				builder.append(j + " " + rnd.nextInt(j) + " " + (rnd.nextInt(1000) + 1) + "\n");
			}
		}
		for (int i = 0; i < 10; i++) {
			builder.append("300 299 10000\n");
			for (int j = 0; j < 10000; j++)
				builder.append(" " + (rnd.nextInt(299) + 1));
			builder.append("\n");
			for (int j = 1; j < 300; j++)
				builder.append(j + " " + rnd.nextInt(j) + " " + (rnd.nextInt(1000) + 1) + "\n");
		}
		return builder.toString();
	}
 
	private void run() {
		//noinspection InfiniteLoopStatement
//		while (true)
		long time = System.currentTimeMillis();
		int testCount = in.readInt();
		for (int i = 0; i < testCount; i++) {
			if (testMode)
				System.err.println("Test #" + i);
			solve();
		}
		if (testMode) {
			System.err.println(System.currentTimeMillis() - time);
			System.err.println(results);
			System.err.println(best);
			System.err.println(total);
		}
		exit();
	}
 
	@SuppressWarnings({"UnusedDeclaration"})
	private void exit() {
		out.close();
		System.exit(0);
	}
 
	@SuppressWarnings({"UnusedDeclaration"})
	private abstract static class InputReader {
		public abstract int read();
 
		public int readInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
 
		public long readLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
 
		public String readString() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuffer res = new StringBuffer();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}
 
		private boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
 
		private String readLine0() {
			StringBuffer buf = new StringBuffer();
			int c = read();
			while (c != '\n' && c != -1) {
				if (c != '\r')
					buf.appendCodePoint(c);
				c = read();
			}
			return buf.toString();
		}
 
		public String readLine() {
			String s = readLine0();
			while (s.trim().length() == 0)
				s = readLine0();
			return s;
		}
 
		public String readLine(boolean ignoreEmptyLines) {
			if (ignoreEmptyLines)
				return readLine();
			else
				return readLine0();
		}
 
		public BigInteger readBigInteger() {
			try {
				return new BigInteger(readString());
			} catch (NumberFormatException e) {
				throw new InputMismatchException();
			}
		}
 
		public char readCharacter() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			return (char) c;
		}
 
		public double readDouble() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			double res = 0;
			while (!isSpaceChar(c) && c != '.') {
				if (c == 'e' || c == 'E')
					return res * Math.pow(10, readInt());
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			}
			if (c == '.') {
				c = read();
				double m = 1;
				while (!isSpaceChar(c)) {
					if (c == 'e' || c == 'E')
						return res * Math.pow(10, readInt());
					if (c < '0' || c > '9')
						throw new InputMismatchException();
					m /= 10;
					res += (c - '0') * m;
					c = read();
				}
			}
			return res * sgn;
		}
 
		public int[] readIntArray(int size) {
			int[] array = new int[size];
			for (int i = 0; i < size; i++)
				array[i] = readInt();
			return array;
		}
 
		public long[] readLongArray(int size) {
			long[] array = new long[size];
			for (int i = 0; i < size; i++)
				array[i] = readLong();
			return array;
		}
 
		public double[] readDoubleArray(int size) {
			double[] array = new double[size];
			for (int i = 0; i < size; i++)
				array[i] = readDouble();
			return array;
		}
 
		public String[] readStringArray(int size) {
			String[] array = new String[size];
			for (int i = 0; i < size; i++)
				array[i] = readString();
			return array;
		}
 
		public char[][] readTable(int rowCount, int columnCount) {
			char[][] table = new char[rowCount][columnCount];
			for (int i = 0; i < rowCount; i++) {
				for (int j = 0; j < columnCount; j++)
					table[i][j] = readCharacter();
			}
			return table;
		}
 
		public void readIntArrays(int[]... arrays) {
			for (int i = 0; i < arrays[0].length; i++) {
				for (int j = 0; j < arrays.length; j++)
					arrays[j][i] = readInt();
			}
		}
	}
 
	private static class StreamInputReader extends InputReader {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar, numChars;
 
		public StreamInputReader(InputStream stream) {
			this.stream = stream;
		}
 
		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
	}
 
	private static class StringInputReader extends InputReader {
		private Reader stream;
		private char[] buf = new char[1024];
		private int curChar, numChars;
 
		public StringInputReader(String stream) {
			this.stream = new StringReader(stream);
		}
 
		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
	}
}
 